class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
        #  Dijkstra
        import heapq
        inf = float('inf')
        short_distance_heap = [(0,startGene)]
        visied = set()
        distance_node = {}
        heapq.heapify(short_distance_heap)
        # 找到其到bank的最短距离
        while short_distance_heap:
            distance,node = heapq.heappop(short_distance_heap)
            for neibor in bank:
                if Diff(node,neibor)==1 and neibor not in visied:
                    visied.add(neibor)
                    if neibor==endGene:
                        return distance+1
                    distance_node[neibor] = distance + 1
                    heapq.heappush(short_distance_heap,(distance_node[neibor],neibor))
        
        return -1

def Diff(s:str,t:str):
    result = 0
    for i in range(len(s)):
        if s[i] != t[i]:
            result += 1
    return result

s = Solution()
r = s.minMutation(startGene=  "AAAAAAAA", endGene=  "CCCCCCCC", bank =
["AAAAAAAA","AAAAAAAC","AAAAAACC","AAAAACCC","AAAACCCC","AACACCCC","ACCACCCC","ACCCCCCC","CCCCCCCA"]
)
print(r)
        

